// 2025/3/30
// https://leetcode.cn/problems/perfect-squares/description/?envType=study-plan-v2&envId=top-100-liked
// 完全平方数

class Solution {
    public:
        int numSquares(int n) {
            vector<int> dp(n + 1, 0);
            for(int i = 1; i <= n; i++)
            {
                dp[i] = INT_MAX;
                for(int j = 1; j * j <= i; j++)
                {
                    dp[i] = min(dp[i], dp[i - j * j]);
                }
                dp[i]++;
            }
            return dp[n];
        }
    };